//
//  26.二叉搜索树与双向链表.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/20.
//

import Foundation
/*
 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 思路：中序遍历即为排序的，还需实现指向，每个节点的左边是左子树最大的，右边是右子树最小的，取小取大取决于遍历方向
 */
func offer_26() {
    /* 测试用例查看剑指offer
     https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
     */
    let root = BinaryTreeNode(4)
    root.leftNode = {
        let node = BinaryTreeNode(2)
        node.leftNode = BinaryTreeNode(1)
        node.rightNode = BinaryTreeNode(3)
        return node
    }()
    root.rightNode = {
        let node = BinaryTreeNode(6)
        node.leftNode = BinaryTreeNode(5)
        node.rightNode = BinaryTreeNode(7)
        return node
    }()
    
    var p = Solution().convert2(root)
    while p != nil {
        print(p!.data)
        p = p?.rightNode
    }
}

fileprivate class Solution {
    private var pre: BinaryTreeNode<Int>? = nil
    // 转换完之后，得到的是链表尾结点
    @discardableResult
    func convert1(_ pRootOfTree: BinaryTreeNode<Int>?) -> BinaryTreeNode<Int>? {
        // write code here
        if let left = pRootOfTree?.leftNode {
            convert1(left)
        }
        pRootOfTree?.leftNode = pre
        pre?.rightNode = pRootOfTree
        pre = pRootOfTree // 左子树最大的
        if let right = pRootOfTree?.rightNode {
            convert1(right)
        }
        return pre
    }
    
    // 优化，逆序排列只需要交换leftNode和rightNode顺序
    @discardableResult
    func convert2(_ pRootOfTree: BinaryTreeNode<Int>?) -> BinaryTreeNode<Int>? {
        // write code here
        if let right = pRootOfTree?.rightNode {
            convert2(right)
        }
        pRootOfTree?.rightNode = pre
        pre?.leftNode = pRootOfTree
        pre = pRootOfTree // 右子树最小的
        if let left = pRootOfTree?.leftNode {
            convert2(left)
        }
        return pre
    }
}


